package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/24 8:53 星期三
 */
public class _21_合并两个有序链表 {
    public static void main(String[] args) {
        ListNode h1 = new ListNode(1);
        ListNode h2 = new ListNode(2);
        ListNode h3 = new ListNode(4);
        ListNode b1 = new ListNode(1);
        ListNode b2 = new ListNode(3);
        ListNode b3 = new ListNode(4);
        h1.next = h2;
        h2.next = h3;
        b1.next = b2;
        b2.next = b3;
//        ListNode listNode = mergeTwoListsTwoPointer(h1, b1);
        ListNode listNode = mergeTwoLists(h1, b1);
        while (listNode != null) {
            System.err.print(listNode.val);
            listNode = listNode.next;
        }
    }

    /**
     * 暴力解法：哑结点法（迭代法）
     * 创建哑结点作为头结点，和一个动态指针辅助哑结点。仅需一次遍历，所以时间复杂度是list1和list2的长度O(m+n)，空间复杂度是O(1)
     * > 2022/08/24 10:14:51
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:40.6 MB,击败了94.47% 的Java用户
     * @param list1 list1
     * @param list2 list2
     * @return ListNode
     */
    private static ListNode mergeTwoListsTwoPointer(ListNode list1, ListNode list2) {
        //创建哑结点，随便给值如-1
        ListNode dumbNode = new ListNode(-1,null);
        //创建动态指针，辅助哑结点，充当其动态尾结点
        ListNode p = dumbNode;
        //若两指针任意走尽，退出循环
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else{
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }

        //循环退出后，仍有可能另一结点不为空，直接让哑结点的动态尾结点指向剩余部分即可
        if (list1 == null){
            p.next = list2;
        }
        if (list2 == null){
            p.next = list1;
        }
        //返回哑结点的第一个有效结点
        return dumbNode.next;
    }

    /**
     * 暴力解法
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            //若list1为空，返回list2
            return list2;
        }
        if (list2 == null) {
            //若list2为空，返回list1
            return list1;
        }
        if (list1.val < list2.val){
            //list1结点比list2结点值小，那么必然要list1进行连接，
            list1.next = mergeTwoLists(list1.next,list2);
        }
        list2.next = mergeTwoLists( list1,list2.next);
        return list1;
    }
    static public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
